package bloomfilter;

import java.util.BitSet;

/**
 * 模拟实现：布隆过滤器
 */
public class BloomFilter {
    private final int[] seeds = new int[] {7, 13, 19, 29};

    private final int DEAFUALT_CAPACITY = 1 << 16;

    // 哈希函数进行映射
    public static class HashReflect {
        private int capacity; // 布隆过滤器的容量
        private int seed;     // 随机的种子
        public HashReflect(int capacity, int seed) {
            this.capacity = capacity;
            this.seed = seed;
        }

        public int hash(String key) {
            int h;
            // 通过 seed 的不同进行 哈希映射
            return (key == null) ? 0 : (seed * (capacity - 1)) & ((h = key.hashCode()) ^ (h >>> 16));
        }
    }

    // 位图
    BitSet bitSet = null;

    HashReflect[] hashReflects = null;

    public BloomFilter() {
        bitSet = new BitSet(DEAFUALT_CAPACITY);
        hashReflects = new HashReflect[seeds.length];

        for (int i = 0; i < seeds.length; i ++) {
            hashReflects[i] = new HashReflect(DEAFUALT_CAPACITY, seeds[i]);
        }
    }

    // 添加到布隆过滤器中
    public void add(String val) {
        for (HashReflect hashReflect : hashReflects) {
            bitSet.set(hashReflect.hash(val));
        }
    }

    // 是否包含, 可能存在误判
    public boolean contains(String val) {
        for (HashReflect hashReflect : hashReflects) {
            if (! bitSet.get(hashReflect.hash(val))) {
                return false;
            }
        }

        return true;
    }

}
